#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int a[100][100];
int dp[100][100][100];
int n, m;

int main() {
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j) {
				a[i][j] = 0;
			}
			else {
				a[i][j] = -1;
			}
		}
	}
	int x, y, w;
	for (int i = 1; i <= m; i++) {
		scanf("%d %d %d", &x, &y, &w);
		dp[0][x][y] = a[x][y] = w;
	}
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				dp[k][i][j] = min(dp[k - 1][i][k], dp[k - 1][i][k] + dp[k - 1][k][j]);
			}
		}
	}
	return 0;
}